



		JOCUL DE-A CONSTRUCTORUL - SOLUTIE
	       ------------------------------------

( data de Dumitru Bogdan)

	Aceasta a fost una dintre cele mai frumoase probleme din concurs,
problema apartinand unui gen cunoscut sub numele de "problema de idee",
necesitand multa imaginatie, vedere in spatiu si, nu in ultimul rand, cu-
nostinte avansate de prelucrarea structurilor mari de date. Programul re-
zultat este foarte scurt, insa rationamentele care stau in spatele lui
sunt migaloase, si interesante de urmarit.
	Mai intai, trebuie stabilit cand problema admite solutie si cand nu.
Pentru aceasta, sa consideram un plan arbitrar de oras; evident, el va avea
cel putin un turn de inaltime maxima. Atunci acel turn va fi, in mod clar,
atat maximul turnurilor privind din fata, cat si din lateral dreapta. In
consecinta, o conditie necesara pentru ca planul sa fie realizabil este
ca maximele celor doua siruri sa fie egale. In continuare, se va demonstra
in mod constructiv ca aceasta conditie este si suficenta.
	Considerand indeplinita aceasta conditie, sa construim orasul cu
un numar minim de blocuri. Notam cu L linia pe care, la vederea din dreapta,
se atinge maximul inaltimilor (daca sunt mai multe, una dintre ele); analog,
notam cu C coloana pe care, la vederea din fata, se atinge maximul inaltimilor
(daca sunt mai multe, una dintre ele). Pentru a satisface cerintele vederii
din fata, asezam pe linia L, corespunzator fiecarei coloane, cate un turn
avand inaltimea citita. Astfel conditiile vederii din fata sunt indeplinite
folosind, evident, un numar minim de blocuri (suma elementelor ce alcatuiesc
primul sir citit). Trecem acum la cerintele vederii din lateral dreapta. Con-
ditia pe linia L este satisfacuta (se vede turnul de inaltime maxima). Parcur-
gem acum restul liniilor. Sa presupunem ca pe o linie ni se cere un turn de
inaltime H, cautam inaltimea H printre cerintele vederii din fata. Daca o gasim,
notam cu CL coloana pe care se afla si "translatam" turnul respctiv pe coloana CL
pana in dreptul liniei cerute. Astfel, satisfacem cerinta vederii din lateral,
iar privind din fata nu s-a schimbat nimic (turnul a "culisat" in lungul unei
coloane, deci nu se vede nici o schimbare). Daca,insa, nu gasim inaltimea
H printre cerintele vederii din fata, suntem nevoiti sa construim un turn de
inaltime H, pe care il plasam pe linia a carei conditie o indeplinim in momen-
tul respctiv, si pe coloana C, fiind astfel "mascat" la privirea din fata de
turnul de inaltime maxima. In acest al doilea caz, numarul total de bolcuri nece-
sare se incrementeaza cu H.
	Sa construim acum orasul cu numar maxim de blocuri. Din nou, vom satisface
intai cerintele vederii din fata. De data aceasta, insa, vom parcurge coloanele si
vom pune pe fiecare linie cate un turn de inaltimea ceruta. Calculam numarul de
blocuri folosite ca fiind suma elementelor primului sir, inmultita cu numarl de linii
al matricei (fiecare turn este pus pe fiecare componenta a coloanei pe care sta el).
Insa daca privim acum din lateral, vedem pe fiecare linie cate un turn de inaltime
maxima. Parcurgem deci liniile si, pe fiecare linie, "taiem" tot ce depaseste inal-
timea ceruta respectivei linii. Notand cu HMAX maximul inaltimilor si H - inaltimea
ceruta liniei curente, vom "taia" (HMAX-H)*(numarul de coloane al matricei de blocuri),
numar ce va trebui scazut din numarul initial de blocuri folosite.